home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_09_08 / 9n08022a < prev    next >
Text File  |  1991-06-19  |  11KB  |  327 lines
  1.  
  2. /* --------------------------------------------------------------
  3.  
  4. CHANGE_NODE: The steps to change a selected node are:
  5.  
  6. A.  Complain if list empty.
  7.  
  8. B.  Get the node number from the user. Note that the first node in the 
  9.     list is number 0, then 1, 2, etc. The number of the node and the 
  10.     subscript it occupies in ary are NOT related even though they can 
  11.     be the same.
  12.  
  13. C.  Traverse list starting at the root node looking for the requested 
  14.     node. When it is found, display its data.
  15.  
  16. D.  Get the replacement data and update node.
  17.  
  18. -------------------------------------------------------------- */
  19.  
  20.         case CHANGE_NODE:
  21.  
  22. /*A*/           if (root_node == EOLIST) {
  23.                         printf("\n   List contains no nodes\n");
  24.                         break;
  25.                 }
  26.  
  27. /*B*/           while (1) {
  28.                         printf("\n   Enter node number: ");
  29.                         scanf("%d", &node);
  30.                         if (node >= 0 && node < nodes_in_use)
  31.                                 break;
  32.  
  33.                         printf("\n   No such node (%d) in list\n", node);
  34.                 }
  35.  
  36. /*C*/           j = root_node;          /* find nth node */
  37.                 for (i = 0; i < node; ++i)
  38.                         j = ary[j].fwd_ptr;
  39.  
  40. /*D*/           printf("\t[%d] => %3d\n", j, ary[j].value);
  41.                 printf("\n   Enter new value: ");
  42.                 scanf("%3d", &ary[j].value);
  43.                 printf("\n   Node changed");
  44.                 break;
  45.  
  46. /* --------------------------------------------------------------
  47.  
  48. SEARCH_FNODE: The steps to find the first node with a given value are:
  49.  
  50. A.  Complain if list empty.
  51.  
  52. B.  Get the required node value from user.
  53.  
  54. C.  Traverse list starting at the root node looking for the node with 
  55.     the requested value.  If it's found, display its data else say 
  56.     there is no such node.
  57.  
  58. -------------------------------------------------------------- */
  59.  
  60.         case SEARCH_FNODE:
  61.  
  62. /*A*/           if (root_node == EOLIST) {
  63.                         printf("\n   List contains no nodes\n");
  64.                         break;
  65.                 }
  66.  
  67. /*B*/           printf("\n   Enter search value: ");
  68.                 scanf("%d", &temp);
  69.  
  70. /*C*/           node = root_node;
  71.                 i = 0;
  72.                 while (node != EOLIST) {
  73.                         if (ary[node].value == temp) {
  74.                                 printf("\tValue %3d found in node %3d\n", 
  75.                                         temp, i);
  76.                                 goto found1;
  77.                         }
  78.                         node = ary[node].fwd_ptr;
  79.                         ++i;
  80.                 }
  81.  
  82.                 printf("\n   No such value (%d) in list\n", temp);
  83. found1:
  84.                 break;
  85.  
  86. /* --------------------------------------------------------------
  87.  
  88. SORT_NODES: The steps to sort the nodes in ascending order of value are:
  89.  
  90. A.  Complain if list empty.
  91.  
  92. B.  Perform a simple bubble sort.
  93.  
  94. -------------------------------------------------------------- */
  95.  
  96.         case SORT_NODES:
  97.  
  98. /*A*/           if (root_node == EOLIST) {
  99.                         printf("\n   List contains no nodes\n");
  100.                         break;
  101.                 }
  102.  
  103. /*B*/           for (i = nodes_in_use - 2; i >= 0; --i) {
  104.                         k = root_node;
  105.                         for (j = 0; j <= i; ++j) {
  106.                                 if (ary[k].value > ary[ary[k].fwd_ptr].value) {
  107.                                         temp = ary[k].value;
  108.                                         ary[k].value = ary[ary[k].fwd_ptr].value;
  109.                                         ary[ary[k].fwd_ptr].value = temp;
  110.                                 }
  111.                                 k = ary[k].fwd_ptr;
  112.                         }
  113.                 }
  114.  
  115.                 printf("\n   Nodes sorted");
  116.                 break;
  117.  
  118.  /* --------------------------------------------------------------
  119.  
  120. INSERT_NODE: The steps to insert a new node in front of an existing
  121. one are:
  122.  
  123. A.  Complain if list empty.
  124.  
  125. B.  Get a new free node from free node list.  If no more, get out.
  126.  
  127. C.  Get the node number from the user. Note that the first node in the 
  128.     list is number 0, then 1, 2, etc. The number of the node and the 
  129.     subscript it occupies in ary are NOT related even though they can 
  130.     be the same.
  131.  
  132. D.  Traverse list starting at the root node looking for the requested 
  133.     node. Then that when we find it we will have gone one node too 
  134.     many so we must keep track of the next-to-current code. 
  135.  
  136. E.  Have a new node so fill it with data.
  137.  
  138. F.  If this is to be the new first node, make it the root otherwise
  139.     update the forward pointer from the previous node to point to
  140.     this new node. Make the new node's forward pointer point to the 
  141.     node we are inserting ahead of.
  142.  
  143. -------------------------------------------------------------- */
  144.  
  145.         case INSERT_NODE:
  146.  
  147. /*A*/           if (root_node == EOLIST) {
  148.                         printf("\n   List contains no nodes\n");
  149.                         break;
  150.                 }
  151.  
  152. /*B*/           if ((new_node = get_free_node()) == EOLIST) {
  153.                         printf("\n   List is full\n");
  154.                         break;
  155.                 }
  156.  
  157. /*C*/           while (1) {
  158.                         printf("\n   Enter number of node to insert before: ");
  159.                         scanf("%d", &node);
  160.                         if (node >= 0 && node < nodes_in_use - 1) /* exclude new node */
  161.                                 break;
  162.  
  163.                         printf("\n   No such node (%d) in list\n", node);
  164.                 }
  165.  
  166. /*D*/           j = root_node;          /* find nth node */
  167.                 for (i = 0; i < node; ++i) {
  168.                         temp = j;
  169.                         j = ary[j].fwd_ptr;
  170.                 }
  171.  
  172. /*E*/           printf("\n   Enter new node's value: ");
  173.                 scanf("%3d", &ary[new_node].value);
  174.  
  175. /*F*/           if (root_node == j)
  176.                         root_node = new_node;
  177.                 else
  178.                         ary[temp].fwd_ptr = new_node;
  179.  
  180.                 ary[new_node].fwd_ptr = j;
  181.                 printf("\n   Node inserted");
  182.                 break;
  183.  
  184. /* --------------------------------------------------------------
  185.  
  186. REMOVE_NODE: The steps to remove a node are:
  187.  
  188. A.  Complain if list empty.
  189.  
  190. B.  Get the node number from the user. Note that the first node in the 
  191.     list is number 0, then 1, 2, etc. The number of the node and the 
  192.     subscript it occupies in ary are NOT related even though they can 
  193.     be the same.
  194.  
  195. C.  Traverse list starting at the root node looking for the requested 
  196.     node. Then that when we find it we will have gone one node too 
  197.     many so we must keep track of the next-to-current code. 
  198.  
  199. D.  If this is the last node make the tail EOLIST otherwise make tail 
  200.     point to the node ahead of this one.
  201.  
  202. E.  If this is the first node, make the root point to its successor 
  203.     node which, if that is EOLIST, is fine. Otherwise make it's 
  204.     predecessor point to the current node's successor.
  205.  
  206. F.  Free the node.
  207.  
  208. -------------------------------------------------------------- */
  209.  
  210.         case REMOVE_NODE:
  211.  
  212. /*A*/           if (root_node == EOLIST) {
  213.                         printf("\n   List contains no nodes\n");
  214.                         break;
  215.                 }
  216.  
  217. /*B*/           while (1) {
  218.                         printf("\n   Enter node number: ");
  219.                         scanf("%d", &node);
  220.                         if (node >= 0 && node < nodes_in_use)
  221.                                 break;
  222.  
  223.                         printf("\n   No such node (%d) in list\n", node);
  224.                 }
  225.  
  226. /*C*/           j = root_node;          /* find nth node */
  227.                 for (i = 0; i < node; ++i) {
  228.                         temp = j;
  229.                         j = ary[j].fwd_ptr;
  230.                 }
  231.  
  232. /*D*/           if (tail_node == j) {
  233.                         if (root_node == j